package com.hermeneute.fsa;

import java.util.Enumeration;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.TreeSet;
public class FSTOperator {
	Hashtable dsmemory;
	Hashtable msmemory;
	HashSet dsmark;
	HashSet msmark;
	HashSet nosinkmark;
	FSTAutomaton first,second,result;
	int newState;
	int sink;
	boolean anotherIteration;
	TreeSet epsilonClosure;
	TreeSet pseudoEquivalent;
	TreeSet newStates;
	
	public FSTOperator() {
		dsmemory = new Hashtable();
		msmemory = new Hashtable();
		dsmark = new HashSet();
		msmark = new HashSet();
	}
	
	
	int getDoubleStateId(FSTDoubleState ds) {
		return ((Integer)dsmemory.get(ds)).intValue();
	}
	
	void markDoubleState(FSTDoubleState ds)
	{
		dsmark.add(ds);
	}
	
	void unmarkDoubleState(FSTDoubleState ds)
	{
		dsmark.remove(ds);
	}
	
	void clearMarkDoubleState()
	{
		dsmark.clear();
	}
	
	boolean isMarkedDoubleState(FSTDoubleState ds)
	{
		return dsmark.contains(ds);
	}
	
	int getMultipleStateId(FSTMultipleState ms) {
		return ((Integer)msmemory.get(ms)).intValue();
	}
	
	void markMultipleState(FSTMultipleState ms)
	{
		msmark.add(ms);
	}
	
	void unmarkMultipleState(FSTMultipleState ms)
	{
		msmark.remove(ms);
	}
	
	void clearMarkMultipleState()
	{
		msmark.clear();
	}
	
	boolean isMarkedMultipleState(FSTMultipleState ms)
	{
		return msmark.contains(ms);
	}
	
	FSTDoubleState makeNewStateUnion(int s1, int s2) {
		FSTDoubleState ds = new FSTDoubleState(s1,s2);
		int cstate = newState;
		if (dsmemory.get(ds) == null) {
			dsmemory.put(ds,new Integer(newState++));
			if ((first.isFinalState(s1))||(second.isFinalState (s2))) {
				// If s1 or s2 is a final state (s1 s2) is a new one 
				result.insertFinalState (cstate);
			}  
		}
		return ds;
	}
	
	public FSTAutomaton computeUnion(FSTAutomaton a,FSTAutomaton b) throws Exception {
		result = new FSTAutomaton();
		first = a;
		second = b;
		newState = 1;
		
		doUnion(first.getStart(),second.getStart());
		
		dsmemory.clear();
		dsmark.clear();
		result.setStart(1);
		result.setFirstFreeState(newState+1);
		return optimize(result);
	}
	
	void doUnion(int s1, int s2) {
		FSTDoubleState ds1 = makeNewStateUnion(s1,s2);
		FSTDoubleState ds2;
		FSTTransitionIterator it;
		int s3, s4;
		
		//System.out.println("doUnion("+s1+","+s2+")");
		if (!isMarkedDoubleState(ds1)) {
			markDoubleState(ds1);
			for(it = first.getTransitions(s1);it.hasNext();) {
				it.next();
				s3 = it.getState();
				s4 = second.nextState(s2,it.getEvent());
				ds2 = makeNewStateUnion(s3,s4);
				doUnion (s3,s4);
				result.addTransition(getDoubleStateId(ds1),
						it.getEvent(),
						getDoubleStateId(ds2));
			}
			for(it = second.getTransitions(s2);it.hasNext();) {
				it.next();
				s4 = it.getState();
				s3 = first.nextState(s1,it.getEvent());
				ds2 = makeNewStateUnion(s3,s4);
				doUnion (s3,s4);
				result.addTransition(getDoubleStateId(ds1),
						it.getEvent(),
						getDoubleStateId(ds2));
			}
		}
	}
	
	
	FSTDoubleState makeNewStateIntersection(int s1, int s2) {
		FSTDoubleState ds = new FSTDoubleState(s1,s2);
		int cstate = newState;
		if (dsmemory.get(ds) == null) {
			//System.out.println("create intersection state ("+s1+","+s2+") = "+newState);
			dsmemory.put(ds,new Integer(newState++));
			if (first.isFinalState(s1)&&second.isFinalState (s2)) {
				//System.out.println(cstate+" is a final state");
				//If s1 and s2 is a final state (s1 s2) is a new one 
				result.insertFinalState (cstate);
			}  
		}
		return ds;
	}
	
	public FSTAutomaton computeIntersection(FSTAutomaton a,FSTAutomaton b) throws Exception {
		result = new FSTAutomaton();
		first = a;
		second = b;
		newState = 1;
		makeNewStateIntersection(first.getStart(),second.getStart());
		sink = newState++;
		doIntersection(first.getStart(),second.getStart());
		
		result.setStart(1);
		result.setFirstFreeState(newState + 1);
		dsmemory.clear();
		dsmark.clear();
		return optimize(result);
	}
	
	void doIntersection(int s1, int s2) {
		FSTDoubleState ds1 = makeNewStateUnion(s1,s2);
		FSTDoubleState ds2;
		FSTTransitionIterator it;
		FSTTransitionIterator it1;
		FSTTransitionIterator it2;
		int s3, s4;
		//System.out.println("doUnion("+s1+","+s2+")");
		if (!isMarkedDoubleState(ds1)) {
			markDoubleState(ds1);
			for(it = first.getTransitions(s1);it.hasNext();) {
				it.next();
				s3 = it.getState();
				s4 = second.nextState(s2,it.getEvent());
				ds2 = makeNewStateIntersection(s3,s4);
				doIntersection(s3,s4);
				result.addTransition(getDoubleStateId(ds1),
						it.getEvent(),
						getDoubleStateId(ds2));
			}
			for(it = second.getTransitions(s2);it.hasNext();) {
				it.next();
				s4 = it.getState();
				s3 = first.nextState(s1,it.getEvent());
				ds2 = makeNewStateIntersection(s3,s4);
				doIntersection (s3,s4);
				result.addTransition(getDoubleStateId(ds1),
						it.getEvent(),
						getDoubleStateId(ds2));
			}
		}
	}
	
	
	boolean caseAddTransition1(FSTDoubleState ds1,
			FSTTransition tr1,
			FSTTransition tr2){
		FSTDoubleState ds2;
		FSTEvent e1,e2,e3;
		int s3, s4, cs1, cs2;
		e1 = tr1.getEvent();
		e2 = tr2.getEvent();
		
		//-----------------------------------------------------------
		// (1) xy-xy,xx-xx,0x-0x,x0-x0,@x-@x,x@-x@,@@-@@,0@-0@, @0-@0
		//-----------------------------------------------------------
		if (tr1.getEvent().equals(tr2.getEvent())){
			//System.out.println("Here");
			s3 = tr1.getState();
			s4 = tr2.getState();
			ds2 = makeNewStateIntersection(s3,s4);
			doIntersection (s3,s4);
			cs1 = ((Integer)dsmemory.get(ds1)).intValue();
			cs2 = ((Integer)dsmemory.get(ds2)).intValue();
			/*System.out.println("addTransition ("
			 +cs1+","
			 +e1.getIn()
			 +":"
			 +e1.getOut()
			 +","+cs2+")"); */
			result.addTransition(cs1,e1,cs2);
			return true;
		} else {
			return false;
		}
	}
	
	
	boolean caseAddTransition3a(FSTDoubleState ds1,
			FSTTransition tr1,
			FSTTransition tr2) {
		FSTDoubleState ds2;
		FSTEvent e1,e2,e3;
		int s3, s4, cs1, cs2;
		e1 = tr1.getEvent();
		e2 = tr2.getEvent();
		
		//----------------------------------------------
		// (3a) [^@][^@]-@@ (xy-@@ ou xx-@@, x0-@@, 0x-@@)
		//----------------------------------------------
		if ((e2.getOut() == FSTEvent.Any) &&
				(e2.getOut() == FSTEvent.Any)) {
			cs1 = ((Integer)dsmemory.get(ds1)).intValue();
			//-----------------------------------------
			// [^@][^@]?
			//-----------------------------------------
			//System.out.println("[^@][^@]-@@ "+cs1+" "+e1.getIn()+" "+e1.getOut());
			if (result.nextState1(cs1,e1) == 0) {
				//System.out.println("[^@][^@]-@@ "+cs1+" "+e1.getIn()+" "+e1.getOut());
				s3 = tr1.getState();
				s4 = tr2.getState();
				ds2 = makeNewStateIntersection(s3,s4);
				doIntersection (s3,s4);
				cs2 = ((Integer)dsmemory.get(ds2)).intValue();
				result.addTransition(cs1,e1,cs2);
			}
			return true;
		} else {
			return false;
		}
	}
	
	boolean caseAddTransition3b(FSTDoubleState ds1,
			FSTTransition tr1,
			FSTTransition tr2) {
		FSTDoubleState ds2;
		FSTEvent e1,e2,e3;
		int s3, s4, cs1, cs2;
		e1 = tr1.getEvent();
		e2 = tr2.getEvent();
		
		//-----------------------------------------------
		// (3b) @@-[^@][^@]    (@@-xy ou @@-xx, @@-x0, @@-0x)
		//-----------------------------------------------
		if ((e2.getOut() != FSTEvent.Any) &&
				(e2.getIn() != FSTEvent.Any)) {
			cs1 = ((Integer)dsmemory.get(ds1)).intValue();
			//-----------------------------------------
			// [^@][^@]?
			//-----------------------------------------
			if (result.nextState1(cs1,e1) == 0) {
				s3 = tr1.getState();
				s4 = tr2.getState();
				ds2 = makeNewStateIntersection(s3,s4);
				doIntersection (s3,s4);
				cs2 = ((Integer)dsmemory.get(ds2)).intValue();
				result.addTransition(cs1,e2,cs2);
			}
			return true;
		} else {
			return false;
		}
	}
	
	void doNextStateIntersection(int s1, int s2) {
		FSTDoubleState ds1 = makeNewStateIntersection(s1,s2);
		FSTDoubleState ds2;
		FSTTransitionIterator it1;
		FSTTransitionIterator it2;
		int s3, s4, cs1, cs2;
		FSTEvent e1,e2,e3;
		
		//System.out.println("doNextStateIntersection("+s1+","+s2+")");
		for(it1 = first.getTransitions(s1);it1.hasNext();) {
			it1.next();
			for(it2 = second.getTransitions(s2);it2.hasNext();) {
				it2.next();
				//System.out.println("Equal");
				caseAddTransition1(ds1,
						it1.getTransition(),
						it2.getTransition());
			}
		}
		for(it2 = second.getTransitions(s2);it2.hasNext();) {
			it2.next();
			for(it1 = first.getTransitions(s1);it1.hasNext();) {
				it1.next();
				//System.out.println("Equal");
				caseAddTransition1(ds1,
						it2.getTransition(),
						it1.getTransition());
			}
		}

		for(it1 = first.getTransitions(s1);it1.hasNext();) {
			it1.next();
			e1 = it1.getEvent();
			if ((e1.getOut() != FSTEvent.Any) &&
					(e1.getIn() != FSTEvent.Any)) {
				//System.out.println("NotAnyNotAny");
				for(it2 = second.getTransitions(s2);it2.hasNext();) {
					it2.next();
					if(caseAddTransition3a(ds1,
							it1.getTransition(),
							it2.getTransition())){}
				}
			} else if ((e1.getOut() == FSTEvent.Any) &&
					(e1.getIn() == FSTEvent.Any)) {
				//System.out.println("AnyAny");
				for(it2 = second.getTransitions(s2);it2.hasNext();) {
					it2.next();
					if(caseAddTransition3b(ds1,
							it1.getTransition(),
							it2.getTransition())){}
				}
			}
		}

		for(it2 = second.getTransitions(s2);it2.hasNext();) {
			it2.next();
			e2 = it2.getEvent();
			if ((e2.getOut() != FSTEvent.Any) &&
					(e2.getIn() != FSTEvent.Any)) {
				//System.out.println("NotAnyNotAny");
				for(it1 = first.getTransitions(s1);it1.hasNext();) {
					it1.next();
					if(caseAddTransition3a(ds1,
							it2.getTransition(),
							it1.getTransition())){}
				}
			} else if ((e2.getOut() == FSTEvent.Any) &&
					(e2.getIn() == FSTEvent.Any)) {
				//System.out.println("AnyAny");
				for(it1 = first.getTransitions(s1);it1.hasNext();) {
					it1.next();
					if(caseAddTransition3b(ds1,
							it2.getTransition(),
							it1.getTransition())){}
				}
			}
		}
	}
	
	public FSTMultipleState computeInitialStateConc(int s){
		FSTMultipleState res = new FSTMultipleState();
		
		res.addState(second.getStart()+first.getFirstFreeState());
		res.addState(s);
		msmemory.put(res,new Integer(s));
		if(second.isFinalState(second.getStart())) {
			result.insertFinalState(s);
		}
		return res;
	}
	
	FSTMultipleState makeNewStateConc(FSTMultipleState ms,FSTEvent e){
		FSTMultipleState ms1 = ms;
		FSTMultipleState ms2 = new FSTMultipleState();
		int s,ns,cs,smaller;
		boolean hitEndConc = false;
		FSTMultipleState res = new FSTMultipleState();
		
		for (Iterator it = ms1.getStates(); it.hasNext();) {
			ns = ((Integer)it.next()).intValue();
			if (ns < first.getFirstFreeState ()) {
				s = first.nextState(ns,e);
				if (s != 0) {
					if (first.isFinalState (s))
					{
						if (second.isFinalState (second.getStart ()))
						{
							hitEndConc = true;
						}			   
						res.addState (second.getStart()+ 
								first.getFirstFreeState());
					}
					res.addState (s);
				}
			} else {
				s = second.nextState(ns-first.getFirstFreeState(),e);
				if (s != 0) {
					if (second.isFinalState (s))
					{
						hitEndConc = true;
					}
					res.addState (s + first.getFirstFreeState ());
				}
			}
		}
		
		//   	System.out.println("firstFreeState = "
		//   			   + first.getFirstFreeState ()
		//   			   + ", "
		//   			   +ms
		//   			   +" "
		//   			   +e.getIn()
		//   			   +":"
		//   			   +e.getOut()
		//   			   +" "
		//   			   +res
		//  			   +" "
		//  			   +hitEndConc
		//   			   );
		if (res.size()==0) return null;
		if (msmemory.get(res) != null) {
			cs = ((Integer)msmemory.get(res)).intValue(); 
			if (hitEndConc) {
				result.insertFinalState (cs);
			}
			return res;
		} else {
			// We reach a state which is a final state of the first automaton 
			// and the start of the second, so its name is the name of the 
			// final state of the first automaton
			//System.out.println(res);
			smaller = res.firstState();
			// 	    System.out.println("smaller = "
			// 			       +smaller
			// 			       +"res.size() ="
			// 			       +res.size()
			// 			       +", "
			// 			       +first.getFirstFreeState());
			if ((res.size() == 2)&& 
					(smaller < first.getFirstFreeState())&&
					(first.isFinalState(smaller))) {
				msmemory.put(res,new Integer (smaller));
			} else if ((res.size() == 1)&& 
					(smaller< first.getFirstFreeState())) {
				// We reach a state of the first automaton which is not final 
				// so we give it its real name and we mark it because 
				// its transitions are known
				msmemory.put(res,new Integer (smaller));
				markMultipleState(res);
			} else {
				msmemory.put(res,new Integer (newState++));
			}
			if (hitEndConc) {
				result.
				insertFinalState(((Integer)msmemory.get(res)).intValue());
			}
		}
		//System.out.println(getMultipleStateId(ms));	
		//System.out.println(getMultipleStateId(res));	
		return res;
	}
	
	public FSTAutomaton computeConc(FSTAutomaton a, FSTAutomaton b) throws Exception {
		int s1,s2,fs;
		FSTMultipleState bs ;
		result = new FSTAutomaton ();
		FSTTransitionIterator it;
		first = a;
		second = b;
		newState = first.getFirstFreeState();
		
		for (Iterator ifs = first.getFinalStates(); ifs.hasNext();) {
			bs=computeInitialStateConc(((Integer)ifs.next()).intValue());
			//System.out.println(bs);
			doConc (bs);
		}
		
		for (Enumeration e = result.getStates(); e.hasMoreElements();) {
			s1 = ((Integer)e.nextElement()).intValue();
			for (it = result.getTransitions(s1);
			it.hasNext();) {
				it.next();
				//s2 = it.getState();
				s2 = result.nextState(s1,it.getEvent());
				// 		System.out.println("replaceTransition ("
				//  				   + s1
				//  				   + ", "
				//  				   +it.getEvent().getIn()
				//  				   +":"
				//  				   +it.getEvent().getOut()
				//  				   +" "
				//  				   +s2
				//  				   +")"
				//  				   );
				
				first.replaceTransition(s1,it.getEvent(),s2);
			}
		}
		
		//for (Enumeration e = first.getFinalStates(); e.hasMoreElements();) {
		//    first.deleteFinalState(e.nextElement());
		//}
		first.deleteFinalState();
		
		for (Iterator ifs = result.getFinalStates(); ifs.hasNext();) {
			fs = ((Integer)ifs.next()).intValue();
			//System.out.println("Adding final state "+fs);
			first.insertFinalState(fs);
		}
		msmemory.clear();
		msmark.clear();
		first.setFirstFreeState(newState+1);
		return optimize(first);
	}
	
	void doConc(FSTMultipleState ms1) {
		FSTMultipleState ms2;
		FSTTransitionIterator it1;
		
		if (!isMarkedMultipleState(ms1)) {
			markMultipleState(ms1);
			for (Iterator it = ms1.getStates();it.hasNext();) {
				Integer is = (Integer)it.next();
				if (is.intValue()<first.getFirstFreeState()){
					for (it1 = first.getTransitions(is);
					it1.hasNext();) {
						it1.next();
						ms2 = makeNewStateConc(ms1,it1.getEvent());
						if (ms2 != null) {
							doConc(ms2);
							//  			    System.out.println("addTransition1 ("
							//  					       + getMultipleStateId(ms1)
							//  					       + ", "
							//  					       +it1.getEvent().getIn()
							//  					       +":"
							//  					       +it1.getEvent().getOut()
							//  					       +" "
							//  					       +getMultipleStateId(ms2)
							//  					       +")"
							//  					       );
							
							result.addTransition(getMultipleStateId(ms1),
									it1.getEvent(),
									getMultipleStateId(ms2));
						}
					}
				}else{
					int tmpState = is.intValue() - first.getFirstFreeState ();
					for (it1 = second.getTransitions(tmpState);
					it1.hasNext();) {
						it1.next();
						ms2 = makeNewStateConc(ms1,it1.getEvent());
						if (ms2 != null) {
							doConc(ms2);
							//  			    System.out.println("addTransition2 ("
							//  					       + getMultipleStateId(ms1)
							//  					       + ", "
							//  					       +it1.getEvent().getIn()
							//  					       +":"
							//  					       +it1.getEvent().getOut()
							//  					       +" "
							//  					       +getMultipleStateId(ms2)
							//  					       +")"
							//  					       );
							
							result.addTransition(getMultipleStateId(ms1),
									it1.getEvent(),
									getMultipleStateId(ms2));
						}
					}
				}
			}
		}
	}
	
	public FSTMultipleState computeInitialStateStar () {
		FSTMultipleState res = new FSTMultipleState ();
		res.addState(first.getStart());
		return res;
	}
	
	FSTMultipleState makeNewStateStar(FSTMultipleState ms, FSTEvent e) {
		FSTMultipleState res = new FSTMultipleState ();
		int s,ns;
		boolean hitStartStar = false;
		
		for (Iterator it = ms.getStates(); it.hasNext();) {
			ns = ((Integer)it.next()).intValue();
			s = first.nextState(ns,e);
			if (s != 0) {
				if (first.isFinalState (s)) {
					hitStartStar = true;
					res.addState(first.getStart ());
				}
				res.addState (s);
			}
		}
		
		if (msmemory.get(res) != null) {
			// 	    System.out.println("key = "
			// 			       +res
			// 			       +", value = "
			// 			       +msmemory.get(res));
			if (hitStartStar) {
				result.insertFinalState (getMultipleStateId(res));
			}
			return res;
		} else {
			msmemory.put(res,new Integer(newState++));
			// 	    System.out.println("key = "
			// 			       +res
			// 			       +", value = "
			// 			       +msmemory.get(res));
			if (hitStartStar) {
				result.insertFinalState (getMultipleStateId(res));
			}
			return res;
		}
	}
	
	public FSTAutomaton computeStar (FSTAutomaton a) throws Exception {
		// FSTEventList *le,*tmple;
		FSTMultipleState startStar;
		result = new FSTAutomaton ();
		first = a;
		second = a;
		newState = 1;
		
		result.setStart (newState);
		result.insertFinalState (newState);
		startStar = computeInitialStateStar ();
		msmemory.put(startStar,new Integer(newState++));
		doStar (startStar);
		result.setFirstFreeState(newState + 1);
		//result.print();
		msmemory.clear ();
		msmark.clear ();
		return optimize(result);
	}
	
	
	void doStar (FSTMultipleState ms1) {
		FSTMultipleState ms2;
		// FSTState s;
		int ns;
		
		if (!isMarkedMultipleState(ms1))
		{
			markMultipleState(ms1);
			
			for (Iterator it = ms1.getStates(); it.hasNext();) {
				ns = ((Integer)it.next()).intValue();
				
				for (FSTTransitionIterator itr = first.getTransitions(ns); 
				itr.hasNext();) { 
					itr.next();
					ms2 =  makeNewStateStar (ms1,itr.getEvent ());
					doStar (ms2);
					result.addTransition(getMultipleStateId(ms1),
							itr.getEvent(),
							getMultipleStateId(ms2));
				}
			}
		}
	}
	
	public FSTAutomaton computeNot (FSTAutomaton a) throws Exception {
		int ns;
		boolean anyAny;
		FSTTransitionIterator itr;
		result = new FSTAutomaton ();
		first = a;
		second = a;
		
		// FSTDoubleStateCell *item1, *item2,*item3;
		
		
		newState = first.getFirstFreeState ();
		result.insertFinalState (newState);
		result.setStart (first.getStart());
		result.addTransition(newState, new FSTEvent((char)2,(char)2),newState);
		
		for(Enumeration e = a.getStates();e.hasMoreElements();) {
			ns = ((Integer)e.nextElement()).intValue();
			anyAny = false;
			if (!first.isFinalState (ns))
			{
				result.insertFinalState (ns);
			}
			for (itr = first.getTransitions(ns);itr.hasNext();)	 {
				itr.next();
				if (itr.getEvent().getOut() == 2&&itr.getEvent().getIn() == 2){
					anyAny = true;
				}
				result.addTransition(ns,itr.getEvent(),itr.getState ());
			}
			if (!anyAny) {
				result.addTransition(ns,
						new FSTEvent((char)2,(char)2),
						newState);
			}
		}
		result.setFirstFreeState(newState + 1);
		msmemory.clear ();
		msmark.clear ();
		return optimize(result);
	}
	
	public FSTAutomaton computeQuestion (FSTAutomaton a) throws Exception {
		result = a;
		result.insertFinalState (result.getStart ());
		return optimize(result);
	}
	
	
	public FSTAutomaton cleanUp (FSTAutomaton a) {
		int i = 1;
		anotherIteration = true;
		
		result = new FSTAutomaton(a);
		//result = a;
		first = a;
		second = a;
		//result.print();
		nosinkmark = new HashSet();
		// While it is possible to find a state from which it is possible to reach a final state we look for such a state
		while (anotherIteration) {
			anotherIteration = false;
			isOnFinalPath (first.getStart (),i++);
			//System.err.println(i+"iterations\n");
		}
		/*first.print();
		 for (Iterator it = dsmark.iterator();it.hasNext();){
		 System.out.println(((Integer)it.next()).intValue());
		 }*/
		dsmemory.clear();
		//dsmark.clear();
		removeSink (first.getStart (),i+1);
		//result.print();
		result.setFirstFreeState(result.getFirstFreeState ()+1);
		dsmark.clear();
		dsmemory.clear ();
		return result;
	}
	
	
	boolean isOnFinalPath (int s1,int iteration) {
		FSTDoubleState ds = new FSTDoubleState(0,s1);
		boolean success = false;
		int s2;
		Integer is1 = new Integer(s1);
		
		//System.out.println("Ici on final path "+iteration+" "+s1+" "+dsmemory);
		if (dsmemory.get(ds) == null || !((Integer)dsmemory.get(ds)).equals(new Integer(iteration))) {
			dsmemory.put(ds,new Integer(iteration));
			//System.out.println("Testing "+s1);
			if (first.isFinalState (s1)) {
				success = true;
				if (!dsmark.contains(is1)) {
					// We note down this state is a good guy
					dsmark.add(is1);
					anotherIteration = true;
				}
			}
			
			for(FSTTransitionIterator it=first.getTransitions(s1);it.hasNext();) {
				it.next();
				s2 = first.nextState(s1,it.getEvent());
				
				if (isOnFinalPath (s2,iteration)) {
					success = true;
					//System.out.println(s1+" is on final path");
					dsmark.add(new Integer(s1));
					if (!dsmark.contains(new Integer(s2))) {
						anotherIteration = true;
						dsmark.add(new Integer(s2));
					}
				}
			}
			return success;
		} else {
			return dsmark.contains(is1);
		}
	}
	
	
	
	boolean removeSink (int s1,int iteration) {
		FSTDoubleState ds = new FSTDoubleState(0,s1);
		boolean isSink = true;
		int s2,asink;
		
		//System.out.println("Ici remove sink "+s1+" "+iteration+" "+dsmemory);
		if (dsmemory.get(ds) == null ||
				!((Integer)dsmemory.get(ds)).equals(new Integer(iteration))) {
			dsmemory.put(ds,new Integer(iteration));
			if (!dsmark.contains(new Integer(s1))) {
				result.deleteState (s1);
				return true;
			} else {
				nosinkmark.add(new Integer(s1));
				isSink = false;
			}
			for(FSTTransitionIterator it=first.getTransitions(s1);it.hasNext();) {
				it.next();
				s2 = first.nextState(s1,it.getEvent());
				if (!removeSink (s2, iteration)) {
					isSink = false;
				} else {
					asink = result.getFirstFreeState ();
					result.replaceTransition (s1,it.getEvent(),asink);
					result.insertSinkState (result.getFirstFreeState ());
				}
			}
			
			if (isSink) {
				//fprintf (stderr,"<2> %d is sink\n",s1);
				//dsmark.remove(new Integer(s1));
				result.deleteState (s1);
				return true;
			}else {
				return false;
			}
		} else{
			return !nosinkmark.contains(new Integer(s1));
		}
	}
	
	public FSTAutomaton optimize (FSTAutomaton a) throws Exception
	{
		FSTAutomaton tmp;
		a = cleanUp(a);
		FSTTransposedAutomaton ta = new FSTTransposedAutomaton(a);
		return  ta.getResult();
	}
	
}
